package com.cuz.daileetcode;

/*****
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线。
 * 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，
 * 但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 *
 * 例子
 * arr=[1,2,100,4]。
 * 开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，
 * 接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿了4之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。
 * arr=[1,100,2]。
 * 开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。
 * 玩家B会获胜，分数为100。所以返回100。
 */
public class Day38 {


    /****
     * 先手拿牌
     *
     * @param arr 所有的牌
     * @param i 从i
     * @param j 拿到j
     * @return 最大可以拿到的牌
     */
    private static int f(int[] arr, int i, int j) {
        //表示是最后一张牌 中间只存在一张
        //先手拿牌的人没有其他选择了 只能这一张
        if (i == j) {
            return arr[i];
        }
        //先手拿 那么会拿i和j 后轮到后手拿，聪明的人会让自己拿到只会为最大
        //如果拿i 那么获得分数arr[i],接下来后手拿 只能拿i+1 到j间的牌了
        //如果拿j 那么获得分数arr[j],接下来后手拿 只能拿i 到j-1间的牌了
        //取二者的最大值
        int peekI = arr[i] + s(arr, i + 1, j);
        int peekJ = arr[j] + s(arr, i, j - 1);
        return Math.max(peekI, peekJ);
    }

    /**
     * 后手拿
     *
     * @param arr
     * @param i
     * @param j
     * @return
     */
    private static int s(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        //后手拿 对手是绝对聪明的人 会让我们拿到轮到我们先手的最小值
        //比如对手拿走i 我们只能拿i+1，j的最小 因为 对手绝对聪明
        //对手拿j 我们只能拿i，j-1的最小
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

    public int winnerScore(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //先手拿的人的分数
        int fScore = f(arr, 0, arr.length - 1);
        //后手拿的人的分数
        int sScore = s(arr, 0, arr.length - 1);
        return Math.max(fScore, sScore);
    }

}
